package com.lishem.top100._08tree;

import com.lishem.common.TreeNode;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/validate-binary-search-tree/description/
 * <p>
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 有效 二叉搜索树定义如下：
 * <p>
 * 节点的左子树只包含 小于 当前节点的数。
 * <p>
 * 节点的右子树只包含 大于 当前节点的数。
 * <p>
 * 所有左子树和右子树自身必须也是二叉搜索树。
 */
public class _08LetCode98_验证二叉搜索树 {


    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                if (pre != null && pre.val > root.val) {
                    return false;
                }
                pre = root;
                root = root.right;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        _08LetCode98_验证二叉搜索树 sol = new _08LetCode98_验证二叉搜索树();
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        System.out.println(sol.isValidBST(root));
    }
}
